Field
The described embodiments relate to operating caches in computing devices. More specifically, the described embodiments relate to a technique for using future accesses of cache blocks in a cache to configure a cache management mechanism.
Related Art
Many modern computing devices include one or more processors or processor cores with a memory hierarchy that includes a mass-storage device, a main memory, and one or more cache memories (or “caches”). In such devices, the mass-storage device is typically a disk drive or a large semiconductor memory (e.g., flash memory) that provides non-volatile storage for a large amount of data and instructions, and the main memory and the caches are typically smaller, faster semiconductor memories (e.g., dynamic random access memories) that provide volatile storage for smaller amounts of data and instructions. In these devices, the caches can be arranged in levels that include a small “level one” (L1) cache for the most rapid access to data and instructions, a larger, sometimes shared, “level two” (L2) cache for less rapid access to data and instructions, and a largest, typically shared, “level three” (L3) cache for the least rapid access (of the caches) to data and instructions. An example device includes four processor cores, each processor core including an internal 96 kilobyte (KB) L1 cache, as well as a 2 megabyte (MB) L2 cache and an 8 MB L3 cache that are each shared by two or more of the processor cores. In addition to these caches, a memory hierarchy for the example computing device includes a 16 GB main memory and a 2 terabyte (TB) mass-storage device.
During operation, data can be retrieved from the mass-storage device and stored in one or more of the caches to enable the more rapid access to the data by the processor cores. However, because the caches in the memory hierarchy are smaller at each level, the caches typically cannot be used to store all of the data that the processor cores may need retrieved from the mass-storage device. The computing device is therefore commonly forced to evict data from a given cache to the next level of the memory hierarchy in order to make space for new data to be stored in the cache.
There have been various techniques proposed for determining the data to be evicted from the main memory and caches. Generally, these techniques rely on past information about the data in the caches such as the recent use of the data, the relative times when data was placed in the cache, the recent data that has been evicted, etc. However, using past information about the data in caches when making eviction decisions can result in inefficient eviction of data from the caches. For example, useful data may be evicted from the cache and therefore not present in the cache for future accesses, which requires a time-consuming retrieval of the data in lower levels of the caches, main memory, or the mass-storage device.